1. Field of the Invention
This invention relates to the manufacture of digital logic systems, and more particularly to the fabrication of integrated circuits.
2. Description of the Relevant Art
Electronic logic circuits (i.e., switching networks) are used in almost every modem device, from automobiles to televisions to washing machines. Logic circuits receive one or more input values and produce one or more output values. There are two basic types of logic circuits: combinational logic circuits and sequential logic circuits. The output values of a combinational logic circuit depend only upon the current input values. The output values of a sequential logic circuit, on the other hand, depend upon both the current input values and the previous input values. Sequential logic circuits (i.e., sequential networks) necessarily include storage elements which enable them to "remember" information about past input values.
A sequential network is composed of a combinational network and one or more storage elements. Storage elements called "flip-flops" sample their input values and change their output values at times determined by a "clocking" signal, and are commonly used in sequential networks. Sequential networks are used to implement "state machines" which accomplish processes having multiple steps. A sequential network implementing a state machine uses one or more "state" values to represent all of the information about past input values required to determine the state machine's future behavior. The storage elements of the sequential network store the state values. The set of all combinations of state values uniquely identify the two or more "states" of the state machine. More and more devices are electronically controlled, and the control units of these devices typically include sequential networks implementing state machines in order to accomplish complex tasks.
Programmable logic devices (PLDs) are commonly used to implement logic networks. PLDs are general-purpose digital components which are manufactured in an "unprogrammed" state, and are later "programmed" to implement a desired logical function. A PLD is typically programmed by a sequence of electrical pulses which configure one or more arrays of programmable switching elements within the PLD. Examples of different types of PLDs include programmable read-only memories (PROMs), field programmable logic arrays (FPLAs), programmable array logic devices (PALs), and field programmable gate arrays (FPGAs). A PROM with m inputs (i.e., address inputs) and n outputs (i.e., data outputs) can be configured to perform any m-input, n-output combinational logic function. FPLAs and PALs have AND and OR arrays. The AND array performs logical AND operations upon input values and their complements, forming product terms. The OR array performs logical OR operations upon the product terms, forming output values. The AND and OR arrays of FPLAs include programmable switching elements, while only the AND arrays of PALs are programmable. FPLAs and PALs implement combinational logic functions as a sum of the product terms (i.e., a sum of products) of input values. FPGAs are semi-custom logic devices including "islands" of programmable logic blocks called "logic cells" surrounded by an interconnection network which includes programmable switching elements. The logical functions performed by the logic cells are determined by programming, as are the interconnections formed between the logic cells. FPLAs, PALs, and FPGAs may also include storage elements (e.g., flip-flops) needed to implement sequential logic circuits.
A PROM with m address inputs and n data outputs includes 2.sup.m .multidot.n programmable switching elements, one for every storage element within the PROM. For example, a 256.times.8 PROM has 8 inputs, 8 outputs, and 2,048 programmable switching elements. The 256.times.8 PROM can be programmed to perform, for example, a multiplication function wherein two 4-bit unsigned binary input values produce an 8-bit product term. As the number of programmable switching elements doubles with each added input, PROMs have difficulty accommodating functions with large numbers of inputs.
An FPLA is a combinational, two-level AND-OR device that can be programmed to realize any sum-of-products logic expression subject to the size limitations of the device. FPLA limitations are the number of inputs, the number of outputs, and the number of product terms. An FPLA with m inputs, n outputs, and p product terms can only perform logic functions having p or fewer product terms. The FPLA includes (2m+n).multidot.p programmable switching elements, compared to the 2.sup.m .multidot.n programmable switching elements within the corresponding PROM. When the number of input variables is small, PROM realizations are more economical than FPLA realizations. FPLA realizations become cost effective when the number of input variables is large. For example, an FPLA with 16 inputs, 8 outputs, and 48 product terms includes 1,920 programmable switching elements. A corresponding 65,536.times.8 PROM would include 524,288 programmable switching elements.
A PAL is also a combinational, two-level AND-OR device subject to the same size limitations as a corresponding FPLA device. As described above, the AND and OR arrays of PLAs include programmable switching elements, while only the AND arrays of PALs are programmable. A PAL with m inputs, n outputs, and p product terms includes 2.sup.m .multidot.p programmable switching elements, compared to the 2.sup.m .multidot.n programmable switching elements within a corresponding PROM and the (2m+n).multidot.p programmable switching elements within the corresponding FPLA. For example, a PAL with 16 inputs, 8 outputs, and 48 product terms includes 1,536 programmable switching elements. The corresponding FPLA includes 1,920 programmable switching elements, and the corresponding 65,539.times.8 PROM would include 524,288 programmable switching elements as described above. PALs achieve economy over PLAs and ROMs by using fewer programmable switching elements to realize logic functions.
A PLD is ultimately configured according to configuration data within a configuration file. The configuration data within the configuration file essentially forms a "logic image" of the function to be performed by the PLD. Few logic designers generate configuration files directly. Most logic designers use PLD design software to specify logic equations symbolically and to generate device configuration files. Modem PLD design programs allow designers to input desired logic functions as Boolean equations, state machine equations, or as expressions of a hardware description language. Some PLD design programs employ schematic capture to determine a desired logic function. Acting much like a computer language compiler, the PLD design program generates PLD configuration files from logic function inputs.
A logic designer considers several factors when selecting a discrete PLD device, among them the required number of input pins, output pins, input/output (I/O) pins, flip-flops, and product terms. The PLD design program aids in simplifying logic equations and selecting a PLD with a sufficient number of input pins, output pins, input/output (I/O) pins, flip-flops, and product terms. In general, the greater the number of logic equations (i.e., outputs), and the greater the number of input variables and state variables required to realize the logic equations, the larger the PLD required to realize the desired logic function.
It is expected that a given device may be required to perform several different logic functions at different times. A straightforward solution to this problem is to design a PLD capable of performing all of the required logic functions, and to issue control signals to direct the performance of each logic function. A drawback of this approach is that the size of the resulting PLD is relatively large in order to realize all of the required logic functions. The cost of a PLD is typically proportional to the number of programmable switching elements within the PLD, thus the relatively large PLD is also costly. In addition, as the logic functions are performed at different times, a large portion of the PLD is inactive at any given time. It would thus be desirable to have a way to dynamically program a relatively small amount of programmable logic to perform logic functions as required.